RL and Markov Decision Process

1. Introduction to RL and MDP
2. Solving MDPs
3. Reinforcement Learning
- 3.1. Model-Based Learning
- 3.2. Model-Free Learning

1. Introduction to RL and MDP

In RL, the world and the agent is modeled by world state \(s_t\in S\) and agent action \(a_t\in A\), where the subscript \(t\) models the time, \(A\) models the action space and \(S\) models the world state space. The transition of world can be modeled by

\[ s_{t+1} \sim \mathbb{P}(s\mid s_0,a_0,\dots, s_t,a_t) \]

In practical, we assume the transitions are Markovian, i.e., the probability of reaching \(s_{t+1}\) from \(s_t\) depends only on \(s_t\) and not on the history of earlier states. This tells

\[ \mathbb{P}(s=s_{t+1}\mid s_0,a_0,\dots,s_t,a_t) = \mathbb{P}(s=s_{t+1}\mid s_t,a_t) \]

We model the transition as \(T(s_t,a_t,s_{t+1})=\mathbb{P}(s=s_{t+1}\mid s_t,a_t)\).

Reward: Reward is also an important component. It acts as a criterion to tell agent if the move is good or not, therefore encouraging the agent to follow a certain pattern. We model the criterion as \(R(s_t,a_t,s_{t+1})\).

A significant difference is that, MDPs have a fixed environment that transitions and rewards are known in advance. However, in RL, these two are unknown.

2. Solving MDPs

Policy: Given the current state, the policy tells which action should be taken. We use \(\pi(s):\mathcal{S}\to \mathcal{A}\) to model policy that produces an action recommended by the policy given the state \(s\).

Starting from initial state \(s_0\), we can alternatively explore actions, state transition and then states again.

state --(take action)--> (s,a) --(transition)--> state'

Here, the \((s,a)\) is an intermediate state: the agent has taken action and is waiting for the world state to transit, aka Q-state, computed by \(Q(s,a)\).

2.1. Utility of State Sequences

The agent produces a sequence of alternating states and actions, and we can compute a sequence of rewards. The utility of the state sequence can model the “goodness” of action sequence. Higher utility can mean better performance of the agent.

We may also involve discounting here. Discounting means that rewards decrease by a multiplier \(\gamma\) as more steps are taken. This can be used to encourage performing useful steps earlier. Discounting also helps utility convergence.

2.2. Optimal Quantities

We use \(V(s)\) to model the utility of a state \(s\), short for expected utility starting from \(s\) and acting optimally. Also use similarly \(Q(s,a)\) to the model the expected utility starting from \(s\), taking action \(a\) and then acting optimally.

With the definition, we can infer their relationship:

\begin{equation} \begin{split} V^\ast(s) &= \max_a Q^\ast (s,a) \\ Q^\ast(s,a) &= \sum_{s'} T(s,a,s')\cdot \Big[ R(s,a,s') + \gamma V^\ast(s') \Big] \end{split} \end{equation}

2.3. Solving Optimal Policy

2.3.1. Value Iteration

We update the value \(V(s)\) for \(k\) rounds to approximate the optimal. i.e.

\[ V_{k+1}(s) \gets \max_a \sum_{s'} T(s,a,s')\Big[ R(s,a,s')+\gamma V_k(s') \Big] \]

Policy extraction. We derive the optimal policy given values

\[ \pi^\ast(s)=\mathop{\text{argmax}}\limits_a \sum_{s'} T(s,a,s')\Big[ R(s,a,s')+\gamma V^\ast(s') \Big] \]

2.3.2. Q-Value Iteration

We start with \(Q_0(s,a)=0\), and iteratively update \(Q\)-values.

\[ Q_{k+1}(s,a) \gets \sum_{s'} T(s,a,s')\Big[ R(s,a,s')+\gamma \max_{a'} Q_k(s',a') \Big] \]

Policy extraction for Q-value iteration is very easy

\[ \pi^\ast(s)=\mathop{\text{argmax}}\limits_a\, Q^\ast(s,a) \]

2.3.3. Policy Iteration

An alternative approach for value iteration. It can be divided into 2 phases.

Policy evaluation. calculate utilities for some fixed policy
Policy improvement. update policy using one-step look-ahead with resulting converged (but not optimal) utilities as future values.

For evaluation with a fixed policy \(\pi\), we can either use iterative updates \( V^\pi_{k+1}(s) \gets \sum_{s'} T(s,\pi(s),s')\Big[ R(s,\pi(s), s') + \gamma V^\pi_k(s') \Big] \), or treat Bellman equations as a linear system: \( V^\pi(s)=\sum_{s'} T(s,\pi(s),s')\Big[ R(s,\pi(s),s')+\gamma V^\pi(s') \Big] \)

Then, we improve our policy with computed value:

\[ \pi_{k+1}(s)=\mathop{\text{argmax}}\limits_a\,\sum_{s'} T(s,a,s')\Big[ R(s,a,s')+\gamma V^{\pi_k}(s') \Big] \]

3. Reinforcement Learning

3.1. Model-Based Learning

Its idea to learn an approximate model based on experience and use this model to solve for values. We first build transition model \(T^e(s,a,s')\) from history and discover each \(R^e(s,a,s')\), where \(e\) stands for empirical. Then with the transition model and reward model, we can solve the RL problem as MDP problem.

3.2. Model-Free Learning

Passive RL: An agent is given a policy to follow and learns the value of states under that policy as it experiences episodes, which is exactly what is done by policy evaluation for MDPs when \(T,R\) are known.
Acitve RL: During active RL, agent can use the feedback it receives to iteratively update it policy while learning until eventually determining the optimal policy after sufficient exploration.

3.2.1. Direct Evaluation

An algorithm under passive RL. We fix some policy \(\pi\) and have the agent experience several episodes while following \(\pi\). As the agent collects samples through these episodes, it maintains counts of the total utilities obtained from each state and the number of times it visited each state. So then, we can compute the estimated value of any state \(s\) by dividing the total utility obtained from \(s\) by the number of times \(s\) was visited.

3.2.2. Temporal Difference Learning

Read: [BROKEN LINK: c5478523-4571-4c44-8459-8e65b7a40b8b]

3.2.3. Q-Learning

Read: [BROKEN LINK: 33e3ca5d-e240-4e85-b718-caa69ab19d5f]